package gold.digger;

import gold.utils.InputUtil;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.TreeMap;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC740 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int deleteAndEarn(int[] nums) {
            TreeMap<Integer, Integer> cnt = new TreeMap<>(Collections.reverseOrder());
            for (int num : nums) {
                cnt.put(num, cnt.getOrDefault(num, 0) + 1);
            }

            List<Integer> numList = new ArrayList<>(cnt.keySet());
            int[] dp = new int[numList.size()];
            dp[0] = numList.get(0) * cnt.get(numList.get(0));
            int res = dp[0];

            for (int i = 1; i < numList.size(); i++) {
                if (numList.get(i) == numList.get(i - 1) - 1) {
                    // 相邻情况
                    int chooseCur = numList.get(i) * cnt.get(numList.get(i)) + (i >= 2 ? dp[i - 2] : 0);
                    dp[i] = Math.max(chooseCur, dp[i - 1]);
                } else {
                    dp[i] = numList.get(i) * cnt.get(numList.get(i)) + dp[i - 1];
                }

                res = Math.max(res, dp[i]);
            }

            return res;
        }
    }


    class Solution_Wrong_by_Greedy {
        public int deleteAndEarn(int[] nums) {
            TreeMap<Integer, Integer> cnt = new TreeMap<>(Collections.reverseOrder());
            for (int num : nums) {
                cnt.put(num, cnt.getOrDefault(num, 0) + 1);
            }

            int res = 0;
            List<Integer> numList = new ArrayList<>(cnt.keySet());
            for (Integer num : numList) {
                if (!cnt.containsKey(num)) continue;
                if (cnt.containsKey(num - 1)) {
                    // 判断num和num-1到底选哪一个
                    if (cnt.get(num - 1) * (num - 1) > num * cnt.get(num) + cnt.getOrDefault(num - 2, 0) * (num - 2)) {
                        res += cnt.get(num - 1) * (num - 1);
                        cnt.remove(num - 1);
                        if (cnt.containsKey(num - 2)) cnt.remove(num - 2);
                    } else {
                        res += num * cnt.get(num);
                        cnt.remove(num - 1);
                    }
                } else res += num * cnt.get(num);

                cnt.remove(num);
            }

            return res;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[1,1,1,2,4,5,5,5,6]");
        System.out.println(solution.deleteAndEarn(arr));
    }

    public static void main(String[] args) throws Exception {
        LC740 an = new LC740();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
